package DynamicProgrammingPackage;

/**
 * @author Lzm
 * @version 1.0
 */
public class canPartition_ {

  // 思路: sum为数组nums的和, 如果能够找到n个数的和为sum / 2, n < nums.length即可
  // 1. dp[i]表示个数为i时, 数组的和为dp[i]
  // 2. 递推公式:
  // dp[j] = Math.max(dp[j],dp[j - weight[i]] + value[i])
  // 3. 初始化: dp[0] = 0;
  // 4. 遍历顺序 先遍历物品在倒序遍历背包

  public boolean canPartition(int[] nums) {
    if (nums.length == 1){
      return false;
    }
    int sum = sum(nums);
    int target = sum / 2;
    if (sum % 2 != 0){
      return false;
    }
    int[] weight = nums;
    int[] value = nums;
    int[] dp = new int[target + 1];
    for (int i = 0 ; i < nums.length ; i++){
      // 倒序遍历背包, 保证nums中一个元素至多能使用一次
      // j代表背包的容量, 容量不能小于物品的所占空间
      for (int j = target ; j >= weight[i] ; j--){
        dp[j] = Math.max(dp[j],dp[j - weight[i]] + value[i]);
      }
    }
    return dp[target] == target ? true : false;
  }
  public int sum(int[] nums){
    int sum = 0;
    for (int num : nums) {
      sum += num;
    }
    return sum;
  }
}
